package 牛客.字符串;

import java.util.HashMap;

/*
  题目描述
        给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
        示例1   输入 [2,3,4,5]      返回值 4
        示例2   输入 [2,2,3,4,3]    返回值 3
 */
public class 最长无重复子串 {
    public int maxLength (int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 1;
        for (int i = 0,j = 0; j < arr.length; j++) {
            if(map.containsKey(arr[j])) {
                i = Math.max(map.get(arr[j]) + 1, i);
                //找到重复的元素后，i需要后移一位，否则位置i的元素会多算一次
                //因为有可能这一次比较的重复的元素的索引会比前一次重复的索引小，所以需要取最大的i索引
            }
            map.put(arr[j],j);
            max = Math.max(j - i + 1,max);
            //每比较完一轮，都应该跟上一轮比较max,取最大值，这样到最后才能得到最长的子串
        }
        return max;
    }

    public static void main(String[] args) {
        最长无重复子串 obj = new 最长无重复子串();
        int[] arr = {1,3,2,3,4,5,6,3,4,1,7};
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(3,3);
        System.out.println(map.get(3));
        map.put(3,5);
        System.out.println(map.get(3));
        System.out.println(obj.maxLength(arr));
    }
}
